//
//  RBTree.hpp
//  RedBlackTree
//
//  Created by 卜绎皓 on 2022/11/17.
//

#pragma once
#include<iostream>
using namespace std;
 
enum Colour
{
    RED,
    BLACK
};//节点的颜色
template<class K,class V>
struct RBTreeNode
{
    RBTreeNode<K,V>* _left;//节点左孩子
    RBTreeNode<K,V>* _right;//节点右孩子
    RBTreeNode<K,V>* _parent;//节点的父亲
    pair<K,V> _kv;//节点中存放的T类型的数据
    Colour _col;//节点的颜色
 
    RBTreeNode(const pair<K,V> kv)
        :_left(nullptr)
        ,_right(nullptr)
        ,_parent(nullptr)
        ,_kv(kv)
        ,_col(RED)
    {}
};
 
template<class K,class V>
class RBTree
{
    typedef RBTreeNode<K, V> Node;
public:
    RBTree()
        :_root(nullptr)
    {}
    //拷贝构造和赋值拷贝也需要自行实现这里不做赘述
    ~RBTree()
    {
        Destory(_root);
        _root = nullptr;
    }
    void Destory(Node* root)
    {
        if (root == nullptr)
        {
            return;
        }
        //利用后序遍历释放节点
        Destory(root->_left);
        Destory(root->_right);
        delete root;
    }
    void RotateR(Node* parent)//右单旋
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
 
        parent->_left = subLR;
        if (subLR != nullptr)//注意:这里一定要判断不为空的，因为下面可能会出现空指针的解引用
        {
            subLR->_parent = parent;
        }
        subL->_right = parent;
        Node* parentParent = parent->_parent;//一定要在改变链接关系之前把这个指针存下来
        parent->_parent = subL;
 
        //if (parentParent == nullptr)或者采用这个条件也是可以的
        if (parent == _root)
        {
            _root = subL;
            _root->_parent = nullptr;
        }
        else
        {
            //这里注意:parent还有父母时，链接之前需要注意判断到底是右孩子还是左孩子
            if (parentParent->_left == parent)
                parentParent->_left = subL;
            else
                parentParent->_right = subL;
 
            subL->_parent = parentParent;//最后还要把父指针关系链接上
        }
    }
    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
 
        //先把subR的左孩子赋值给parent的右节点
        parent->_right = subRL;
        if (subRL != nullptr)//注意一定要判断是否为空的情况
        {
            subRL->_parent = parent;//然后链接parent指针
        }
 
        //然后subR的左节点链接上parent
        subR->_left = parent;
        Node* parentParent = parent->_parent;//提前记录
        parent->_parent = subR;
        //if (parentParent == nullptr)
        if (parent == _root)
        {
            _root = subR;
            _root->_parent = nullptr;
        }
        else
        {
            if (parentParent->_left == parent)
                parentParent->_left = subR;
            else
                parentParent->_right = subR;
 
            subR->_parent = parentParent;
        }
    }
    pair<Node*, bool> Insert(const pair<K, V> kv)
    {
        if (_root == nullptr)
        {
            _root = new Node(kv);
            _root->_col = BLACK;//根节点给黑色
            return make_pair(_root, true);
        }
 
        Node* cur = _root;
        Node* parent = nullptr;
        while (cur)//循环去找空位
        {
            if (kv.first > cur->_kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if(kv.first < cur->_kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return make_pair(cur, false);
            }
        }
 
        Node* newnode = new Node(kv);
        newnode->_col = RED;//链接上新节点
        if (kv.first > parent->_kv.first)
        {
            parent->_right = newnode;
            newnode->_parent = parent;
        }
        else
        {
            parent->_left = newnode;
            newnode->_parent = parent;
        }
        cur = newnode;
 
        //父节点存在且父节点为红色时需要继续处理
        while (parent && parent->_col == RED)
        {
            Node* grandfather = parent->_parent;
            //关键看叔叔的脸色
            if (parent == grandfather->_left)
            {
                Node* uncle = grandfather->_right;
                if (uncle && uncle->_col == RED)
                {
                    //具体变色的情况需要画图分析:
                    grandfather->_col = RED;
                    parent->_col = uncle->_col = BLACK;
 
                    //注意需要继续向上处理,容易忘记
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else
                {
                    if (cur == parent->_left)
                    {
                        RotateR(grandfather);//右单旋
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else
                    {
                        RotateL(parent);//先以父节点为旋转点左旋
                        RotateR(grandfather);//再以g为旋转点右旋
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;//旋转+变色过后一定是满足所有性质的直接退出循环
                }
            }
            else
            {
                Node* uncle = grandfather->_left;
                if (uncle && uncle->_col == RED)
                {
                    uncle->_col = parent->_col = BLACK;
                    grandfather->_col = RED;
 
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else // 情况2：+ 情况3：
                {
                    if (cur == parent->_right)
                    {
                        RotateL(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else // cur == parent->_left
                    {
                        RotateR(parent);
                        RotateL(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            }
        }
        _root->_col = BLACK;
        return make_pair(newnode, true);
    }
    void _InOrder(Node* root)//中序遍历递归打印
    {
        if (root == nullptr)
        {
            return;
        }
 
        _InOrder(root->_left);
        cout << root->_kv.first << ":"<<root->_kv.second<<endl;
        _InOrder(root->_right);
    }
    void InOrder()
    {
        _InOrder(_root);
        cout << endl;
    }
    bool _CheckBlance(Node* root, int blackNum, int count)//balckNum相当于一个标尺，count就是用来记录每条路径的黑节点数目
    {
        if (root == nullptr)//如果root走到空节点
        {
            if (count != blackNum)//count不等于最左路径的黑色节点数
            {
                cout << "黑色节点的数量不相等" << endl;
                return false;//返回假
            }
            return true;//否则返回真
        }
        if (root->_col == RED && root->_parent->_col == RED)
        {
            cout << "存在连续的红色节点" << endl;
            return false;
        }
        if (root->_col == BLACK)
        {
            count++;
        }
        return _CheckBlance(root->_left, blackNum, count)
            && _CheckBlance(root->_right, blackNum, count);//再递归到各子树的子问题
    }
    bool CheckBlance()
    {
        if (_root == nullptr)
        {
            return true;
        }
        if (_root->_col == RED)
        {
            cout << "根节点是红色的" << endl;
            return false;
        }
        // 找最左路径做黑色节点数量参考值
        int blackNum = 0;
        Node* left = _root;
        while (left)
        {
            if (left->_col == BLACK)
            {
                blackNum++;
            }
            left = left->_left;
        }
        int count = 0;
        return _CheckBlance(_root, blackNum, count);
    }
private:
    Node* _root;
};
